package com.jiang.专题.动态规划.Q474;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/07 22:06
 */
class Solution {
    // 0-1背包问题
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j] 表示 当有i个0、j个1时，子集为多大
        for (String str: strs) {
            int num_0 = 0;
            int num_1 = 0;
            for (int k = 0; k < str.length(); k++) {
                if (str.charAt(k) == '0') num_0++;
                else num_1++;
            }
            for (int i = m; i >= num_0; i--) {
                for (int j = n; j >= num_1; j--) {
                    dp[i][j] = Math.max(dp[i - num_0][j - num_1] + 1, dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }
}
